package main

//func main() {
//	println(strArrToString(letterCombinations("2233")))
//}

func letterCombinations(digits string) []string {
	numberMap := map[rune][]string{
		'2': {"a", "b", "c"},
		'3': {"d", "e", "f"},
		'4': {"g", "h", "i"},
		'5': {"j", "k", "l"},
		'6': {"m", "n", "o"},
		'7': {"p", "q", "r", "s"},
		'8': {"t", "u", "v"},
		'9': {"w", "x", "y", "z"},
	}

	sLen := len(digits)
	if sLen == 0 {
		return []string{}
	}

	if sLen == 1 {
		return numberMap[rune(digits[0])]
	}

	result := backtrack(0, sLen, digits, []string{}, numberMap, "")
	return result
}

func backtrack(index int, sLen int, digits string, result []string, numberMap map[rune][]string, word string) []string {
	if index == sLen {
		return append(result, word)
	}

	for _, tn := range numberMap[rune(digits[index])] {
		result = backtrack(index+1, sLen, digits, result, numberMap, word+tn)
	}
	return result
}
